pyrobot/0040755000076400003100000000000010423165120012231 5ustar dblankfacultypyrobot/Makefile0100755000076400003100000000261510423165120013675 0ustar dblankfaculty# Main Makefile for the Pyrobot Python Robotics System # Please edit Makefile.cfg, or run "make config; make" # Need a guess to get started: PYTHON_BIN=python include Makefile.cfg # Failing subdir: robot/driver/testc SUBDIRS = $(CONFIGDIRS) everything: system/version.py all compile bin/pyrobot include Makefile.src .PHONY: all tar pyrobot-$(PYROBOT_VERSION).tgz clean compile tar: pyrobot-$(PYROBOT_VERSION).tgz config: system/version.py $(PYTHON_BIN) configure.py make compile: $(PYTHON_BIN) compile.py pyrobot-$(PYROBOT_VERSION).tgz: Makefile mkdir download || true mv *.tgz download/ || true make clean; cd ..; tar cfz pyrobot-$(PYROBOT_VERSION).tgz --exclude fedora --exclude stylesheet.css --exclude knoppix --exclude CVS --exclude tars --exclude download --exclude Makefile.cfg pyrobot; mv pyrobot-$(PYROBOT_VERSION).tgz pyrobot; cd -; mv *.tgz download $(RM) -f download/pyrobot-latest.tgz cd download; ln -s pyrobot-$(PYROBOT_VERSION).tgz pyrobot-latest.tgz Makefile.cfg: $(PYTHON_BIN) configure.py system/version.py: Makefile.src echo -e "# This file is automatically generated\ndef version():\n\treturn \"$(PYROBOT_VERSION)\"" > system/version.py bin/pyrobot: Makefile.cfg Makefile Makefile.src build/pyrobot system/version.py echo -e "#!$(PYTHON_BIN)" > bin/pyrobot cat build/pyrobot >> bin/pyrobot chmod a+x bin/pyrobot clean:: - $(RM) system/version.py - $(RM) bin/pyrobot pyrobot/AUTHORS0100644000076400003100000000216510250174516013311 0ustar dblankfacultyContributors to Pyro: Mohammad Arrabi, University of Arkansas, Fayetteville Douglas Blank, Bryn Mawr College Ioana Butoi, Bryn Mawr College Robert Casey, UMass-Lowell Kevin Coogan, College of Charleston Chris Couples, Bryn Mawr College Zachary Dodds, Harvey Mudd College Matt Fiedler, Swarthmore College Kurt Konologe, SRI International Jeniffer Franklin, College of Charleston Ethan Jucovy, Swarthmore College Deepak Kumar, Bryn Mawr College Bill Manaris, College of Charleston Jim Marshall, Pomona College Bruce Maxwell, Swarthmore College Stephen McCaul, University of Arkansas, Fayatteville Lisa Meeden, Swarthmore College Ananya Misra, Bryn Mawr College Evan Moses, Swarthmore College Willi Richert, C-Lab, Germany George Sakkis, Rutgers Daniel Sproul, Swarthmore College Jeremy Stober, Swarthmore College Andrew Stout, Swarthmore College Yee Lin Tan, Swarthmore College Cassandra Telenco, High School Student (Swarthmore College) Stefanie Tellex, MIT Darby Thompson, Bryn Mawr College Ben Turner, Swarthmore College Shaun Vincent, College of Charleston Kim Wheeler, Road Narrows, Inc. Holly Yanco, University of Massachussetts-Lowell pyrobot/ai/0040755000076400003100000000000010271174330012626 5ustar dblankfacultypyrobot/ai/__init__.py0100755000076400003100000000000007627023362014736 0ustar dblankfacultypyrobot/ai/gaqueens.py0100755000076400003100000000465210244170211015011 0ustar dblankfacultyfrom pyrobot.brain.ga import * def safe_queen(new_row, new_col, sol): for row in range(new_row): if (sol[row] == new_col or sol[row] + row == new_col + new_row or sol[row] - row == new_col - new_row): return 0 return 1 def fitness(sol): set = [] row = 0 sum = 0 for col in sol: set.append( col ) if col < 0 or col >= len(sol): return 0 sum += safe_queen( row, col, set) row += 1 previous = -1 for col in sol: # see how far apart each is, normalize, add to sum if previous == -1: bonus = 0.0 else: bonus += abs(col - previous) previous = col return sum + 1 - (bonus / ((len(sol) - 1) * len(sol))) #return sum class GAQueens(GA): def fitnessFunction(self, genePos): return fitness( self.pop.individuals[genePos].genotype) def isDone(self): self.pop.bestMember.display() fit = fitness( self.pop.bestMember.genotype) print "Best Fitness:", fit return fit == len(self.pop.bestMember.genotype) class MyGene(Gene): def display(self): for row in range(len(self.genotype)): for col in self.genotype: if col == row: print "X", else: print ".", print "" if __name__ == '__main__': ga = GAQueens(Population(300, MyGene, size = 16, mode = 'integer', max = 16,min = 0, maxStep = 1, verbose = 1, elitePercent = .01, crossoverPoints = 0), verbose = 1, mutateRate = .3, crossoverRate = .75) ga.evolve() # after 83 generations: # mygene = MyGene(size = 16) # mygene.data = [8, 1, 7, 13, 6, 0, 9, 5, 12, 15, 3, 10, 2, 14, 11, 4] # mygene.display() # # . . . . . X . . . . . . . . . . # . X . . . . . . . . . . . . . . # . . . . . . . . . . . . X . . . # . . . . . . . . . . X . . . . . # . . . . . . . . . . . . . . . X # . . . . . . . X . . . . . . . . # . . . . X . . . . . . . . . . . # . . X . . . . . . . . . . . . . # X . . . . . . . . . . . . . . . # . . . . . . X . . . . . . . . . # . . . . . . . . . . . X . . . . # . . . . . . . . . . . . . . X . # . . . . . . . . X . . . . . . . # . . . X . . . . . . . . . . . . # . . . . . . . . . . . . . X . . # . . . . . . . . . X . . . . . . pyrobot/ai/queens.py0100755000076400003100000000213707627023362014514 0ustar dblankfacultydef n_queens(n, width): if n == 0: return [[]] else: return add_queen(n-1, width, n_queens(n-1, width)) def add_queen(new_row, width, previous_solutions): solutions = [] for sol in previous_solutions: for new_col in range(width): if safe_queen(new_row, new_col, sol): solutions.append(sol + [new_col]) return solutions def safe_queen(new_row, new_col, sol): for row in range(new_row): if (sol[row] == new_col or sol[row] + row == new_col + new_row or sol[row] - row == new_col - new_row): return 0 return 1 def check_solution(sol): set = [] row = 0 for col in sol: set.append( col ) if not safe_queen( row, col, set): return 0 row += 1 return 1 def fitness(sol): set = [] row = 0 sum = 0 for col in sol: set.append( col ) if col < 0: return 0 sum += safe_queen( row, col, set) row += 1 return sum if __name__ == '__main__': for sol in n_queens(8, 8): print sol pyrobot/aima/0040755000076400003100000000000010271174330013144 5ustar dblankfacultypyrobot/aima/__init__.py0100644000076400003100000000000010144027257015244 0ustar dblankfacultypyrobot/aima/agents.py0100644000076400003100000005051210147236242015002 0ustar dblankfaculty"""Implement Agents and Environments (Chapters 1-2). The class hierarchies are as follows: Object ## A physical object that can exist in an environment Agent Wumpus RandomAgent ReflexVacuumAgent ... Dirt Wall ... Environment ## An environment holds objects, runs simulations XYEnvironment VacuumEnvironment WumpusEnvironment EnvFrame ## A graphical representation of the Environment """ from utils import * import random, copy #______________________________________________________________________________ class Object: """This represents any physical object that can appear in an Environment. You subclass Object to get the objects you want. Each object can have a .__name__ slot (used for output only).""" def __init__(self, image = None): self.image = image def __repr__(self): return '<%s>' % getattr(self, '__name__', self.__class__.__name__) def is_alive(self): """Objects that are 'alive' should return true.""" return hasattr(self, 'alive') and self.alive def display(self, canvas, x, y, width, height): """Display an image of this Object on the canvas.""" pass class Agent(Object): """An Agent is a subclass of Object with one required slot, .program, which should hold a function that takes one argument, the percept, and returns an action. (What counts as a percept or action will depend on the specific environment in which the agent exists.) Note that 'program' is a slot, not a method. If it were a method, then the program could 'cheat' and look at aspects of the agent. It's not supposed to do that: the program can only look at the percepts. An agent program that needs a model of the world (and of the agent itself) will have to build and maintain its own model. There is an optional slots, .performance, which is a number giving the performance measure of the agent in its environment.""" def __init__(self, image = None): Object.__init__(self, image) def program(percept): return raw_input('Percept=%s; action? ' % percept) self.program = program self.alive = True def TraceAgent(agent): """Wrap the agent's program to print its input and output. This will let you see what the agent is doing in the environment.""" old_program = agent.program def new_program(percept): action = old_program(percept) print '%s perceives %s and does %s' % (agent, percept, action) return action agent.program = new_program return agent #______________________________________________________________________________ class TableDrivenAgent(Agent): """This agent selects an action based on the percept sequence. It is practical only for tiny domains. To customize it you provide a table to the constructor. [Fig. 2.7]""" def __init__(self, table): "Supply as table a dictionary of all {percept_sequence:action} pairs." ## The agent program could in principle be a function, but because ## it needs to store state, we make it a callable instance of a class. Agent.__init__(self) percepts = [] def program(percept): percepts.append(percept) action = table.get(tuple(percepts)) return action self.program = program class RandomAgent(Agent): "An agent that chooses an action at random, ignoring all percepts." def __init__(self, actions): Agent.__init__(self) self.program = lambda percept: random.choice(actions) #______________________________________________________________________________ loc_A, loc_B = (0, 0), (1, 0) # The two locations for the Vacuum world class ReflexVacuumAgent(Agent): "A reflex agent for the two-state vacuum environment. [Fig. 2.8]" def __init__(self): Agent.__init__(self) def program((location, status)): if status == 'Dirty': return 'Suck' elif location == loc_A: return 'Right' elif location == loc_B: return 'Left' self.program = program def RandomVacuumAgent(): "Randomly choose one of the actions from the vaccum environment." return RandomAgent(['Right', 'Left', 'Suck', 'NoOp']) def TableDrivenVacuumAgent(): "[Fig. 2.3]" table = {((loc_A, 'Clean'),): 'Right', ((loc_A, 'Dirty'),): 'Suck', ((loc_B, 'Clean'),): 'Left', ((loc_B, 'Dirty'),): 'Suck', ((loc_A, 'Clean'), (loc_A, 'Clean')): 'Right', ((loc_A, 'Clean'), (loc_A, 'Dirty')): 'Suck', # ... ((loc_A, 'Clean'), (loc_A, 'Clean'), (loc_A, 'Clean')): 'Right', ((loc_A, 'Clean'), (loc_A, 'Clean'), (loc_A, 'Dirty')): 'Suck', # ... } return TableDrivenAgent(table) class ModelBasedVacuumAgent(Agent): "An agent that keeps track of what locations are clean or dirty." def __init__(self): Agent.__init__(self) model = {loc_A: None, loc_B: None} def program((location, status)): "Same as ReflexVacuumAgent, except if everything is clean, do NoOp" model[location] = status ## Update the model here if model[loc_A] == model[loc_B] == 'Clean': return 'NoOp' elif status == 'Dirty': return 'Suck' elif location == loc_A: return 'Right' elif location == loc_B: return 'Left' self.program = program #______________________________________________________________________________ class Environment: """Abstract class representing an Environment. 'Real' Environment classes inherit from this. Your Environment will typically need to implement: percept: Define the percept that an agent sees. execute_action: Define the effects of executing an action. Also update the agent.performance slot. The environment keeps a list of .objects and .agents (which is a subset of .objects). Each agent has a .performance slot, initialized to 0. Each object has a .location slot, even though some environments may not need this.""" def __init__(self,): self.objects = []; self.agents = [] object_classes = [] ## List of classes that can go into environment def percept(self, agent): "Return the percept that the agent sees at this point. Override this." abstract() def execute_action(self, agent, action): "Change the world to reflect this action. Override this." abstract() def default_location(self, object): "Default location to place a new object with unspecified location." return None def exogenous_change(self): "If there is spontaneous change in the world, override this." pass def is_done(self): "By default, we're done when we can't find a live agent." for agent in self.agents: if agent.is_alive(): return False return True def step(self): """Run the environment for one time step. If the actions and exogenous changes are independent, this method will do. If there are interactions between them, you'll need to override this method.""" if not self.is_done(): actions = [agent.program(self.percept(agent)) for agent in self.agents] for (agent, action) in zip(self.agents, actions): self.execute_action(agent, action) self.exogenous_change() def run(self, steps=1000): """Run the Environment for given number of time steps.""" for step in range(steps): if self.is_done(): return self.step() def add_object(self, object, location=None): """Add an object to the environment, setting its location. Also keep track of objects that are agents. Shouldn't need to override this.""" object.location = location or self.default_location(object) self.objects.append(object) if isinstance(object, Agent): object.performance = 0 self.agents.append(object) return self class XYEnvironment(Environment): """This class is for environments on a 2D plane, with locations labelled by (x, y) points, either discrete or continuous. Agents perceive objects within a radius. Each agent in the environment has a .location slot which should be a location such as (0, 1), and a .holding slot, which should be a list of objects that are held """ def __init__(self, width=10, height=10): update(self, objects=[], agents=[], width=width, height=height) def objects_at(self, location): "Return all objects exactly at a given location." return [obj for obj in self.objects if obj.location == location] def objects_near(self, location, radius): "Return all objects within radius of location." radius2 = radius * radius return [obj for obj in self.objects if distance2(location, obj.location) <= radius2] def percept(self, agent): "By default, agent perceives objects within radius r." return [self.object_percept(obj, agent) for obj in self.objects_near(agent)] def execute_action(self, agent, action): if action == 'TurnRight': agent.heading = turn_heading(agent.heading, -1) elif action == 'TurnLeft': agent.heading = turn_heading(agent.heading, +1) elif action == 'Forward': self.move_to(agent, vector_add(agent.heading, agent.location)) elif action == 'Grab': objs = [obj for obj in self.objects_at(agent.location) if obj.is_grabable(agent)] if objs: agent.holding.append(objs[0]) elif action == 'Release': if agent.holding: agent.holding.pop() agent.bump = False def object_percept(self, obj, agent): #??? Should go to object? "Return the percept for this object." return obj.__class__.__name__ def default_location(self, object): return (random.choice(self.width), random.choice(self.height)) def move_to(object, destination): "Move an object to a new location." def add_object(self, object, location=(1, 1)): Environment.add_object(self, object, location) object.holding = [] object.held = None self.objects.append(object) def add_walls(self): "Put walls around the entire perimeter of the grid." for x in range(self.width): self.add_object(Wall(), (x, 0)) self.add_object(Wall(), (x, self.height-1)) for y in range(self.height): self.add_object(Wall(), (0, y)) self.add_object(Wall(), (self.width-1, y)) def turn_heading(self, heading, inc, headings=[(1, 0), (0, 1), (-1, 0), (0, -1)]): "Return the heading to the left (inc=+1) or right (inc=-1) in headings." return headings[(headings.index(heading) + inc) % len(headings)] #______________________________________________________________________________ ## Vacuum environment class TrivialVacuumEnvironment(Environment): """This environment has two locations, A and B. Each can be Dirty or Clean. The agent perceives its location and the location's status. This serves as an example of how to implement a simple Environment.""" def __init__(self): Environment.__init__(self) self.status = {loc_A:random.choice(['Clean', 'Dirty']), loc_B:random.choice(['Clean', 'Dirty'])} def percept(self, agent): "Returns the agent's location, and the location status (Dirty/Clean)." return (agent.location, self.status[agent.location]) def execute_action(self, agent, action): """Change agent's location and/or location's status; track performance. Score 10 for each dirt cleaned; -1 for each move.""" if action == 'Right': agent.location = loc_B agent.performance -= 1 elif action == 'Left': agent.location = loc_A agent.performance -= 1 elif action == 'Suck': if self.status[agent.location] == 'Dirty': agent.performance += 10 self.status[agent.location] = 'Clean' def default_location(self, object): "Agents start in either location at random." return random.choice([loc_A, loc_B]) class Dirt(Object): pass class Wall(Object): pass class VacuumEnvironment(XYEnvironment): """The environment of [Ex. 2.12]. Agent perceives dirty or clean, and bump (into obstacle) or not; 2D discrete world of unknown size; performance measure is 100 for each dirt cleaned, and -1 for each turn taken.""" def __init__(self, width=10, height=10): XYEnvironment.__init__(self, width, height) self.add_walls() object_classes = [Wall, Dirt, ReflexVacuumAgent, RandomVacuumAgent, TableDrivenVacuumAgent, ModelBasedVacuumAgent] def percept(self, agent): """The percept is a tuple of ('Dirty' or 'Clean', 'Bump' or 'None'). Unlike the TrivialVacuumEnvironment, location is NOT perceived.""" status = if_(self.find_at(Dirt, agent.location), 'Dirty', 'Clean') bump = if_(agent.bump, 'Bump', 'None') return (status, bump) def execute_action(self, agent, action): if action == 'Suck': if self.find_at(Dirt, agent.location): agent.performance += 100 agent.performance -= 1 XYEnvironment.execute_action(self, agent, action) #______________________________________________________________________________ class SimpleReflexAgent(Agent): """This agent takes action based solely on the percept. [Fig. 2.13]""" def __init__(self, rules, interpret_input): Agent.__init__(self) def program(percept): state = interpret_input(percept) rule = rule_match(state, rules) action = rule.action return action self.program = program class ReflexAgentWithState(Agent): """This agent takes action based on the percept and state. [Fig. 2.16]""" def __init__(self, rules, udpate_state): Agent.__init__(self) state, action = None, None def program(percept): state = update_state(state, action, percept) rule = rule_match(state, rules) action = rule.action return action self.program = program #______________________________________________________________________________ ## The Wumpus World class Gold(Object): pass class Pit(Object): pass class Arrow(Object): pass class Wumpus(Agent): pass class Explorer(Agent): pass class WumpusEnvironment(XYEnvironment): object_classes = [Wall, Gold, Pit, Arrow, Wumpus, Explorer] def __init__(self, width=10, height=10): XYEnvironment.__init__(self, width, height) self.add_walls() ## Needs a lot of work ... #______________________________________________________________________________ def compare_agents(EnvFactory, AgentFactories, n=10, steps=1000): """See how well each of several agents do in n instances of an environment. Pass in a factory (constructor) for environments, and several for agents. Create n instances of the environment, and run each agent in copies of each one for steps. Return a list of (agent, average-score) tuples.""" envs = [EnvFactory() for i in range(n)] return [(A, test_agent(A, steps, copy.deepcopy(envs))) for A in AgentFactories] def test_agent(AgentFactory, steps, envs): "Return the mean score of running an agent in each of the envs, for steps" total = 0 for env in envs: agent = AgentFactory() env.add_object(agent) env.run(steps) total += agent.performance return float(total)/len(envs) #______________________________________________________________________________ _docex = """ a = ReflexVacuumAgent() a.program a.program((loc_A, 'Clean')) ==> 'Right' a.program((loc_B, 'Clean')) ==> 'Left' a.program((loc_A, 'Dirty')) ==> 'Suck' a.program((loc_A, 'Dirty')) ==> 'Suck' e = TrivialVacuumEnvironment() e.add_object(TraceAgent(ModelBasedVacuumAgent())) e.run(5) ## Environments, and some agents, are randomized, so the best we can ## give is a range of expected scores. If this test fails, it does ## not necessarily mean something is wrong. envs = [TrivialVacuumEnvironment() for i in range(100)] def testv(A): return test_agent(A, 4, copy.deepcopy(envs)) testv(ModelBasedVacuumAgent) (7 < _ < 11) ==> True testv(ReflexVacuumAgent) (5 < _ < 9) ==> True testv(TableDrivenVacuumAgent) (2 < _ < 6) ==> True testv(RandomVacuumAgent) (0.5 < _ < 3) ==> True """ #______________________________________________________________________________ # GUI - Graphical User Interface for Environments # If you do not have Tkinter installed, either get a new installation of Python # (Tkinter is standard in all new releases), or delete the rest of this file # and muddle through without a GUI. import Tkinter as tk from ImageTk import PhotoImage import Image class EnvFrame(tk.Frame): def __init__(self, env, title='AIMA GUI', cellwidth=50, n=10): update(self, cellwidth = cellwidth, running=False, delay=1.0) self.n = n self.running = 0 self.delay = 1.0 self.env = env tk.Frame.__init__(self, None, width=(cellwidth+2)*n, height=(cellwidth+2)*n) self.winfo_toplevel().title(title) # Toolbar toolbar = tk.Frame(self, relief='raised', bd=2) toolbar.pack(side='top', fill='x') for txt, cmd in [('Step >', self.env.step), ('Run >>', self.run), ('Stop [ ]', self.stop)]: tk.Button(toolbar, text=txt, command=cmd).pack(side='left') tk.Label(toolbar, text='Delay').pack(side='left') scale = tk.Scale(toolbar, orient='h', from_=0.0, to=10, resolution=0.5, command=lambda d: setattr(self, 'delay', d)) scale.set(self.delay) scale.pack(side='left') # Canvas for drawing on self.canvas = tk.Canvas(self, width=(cellwidth+1)*n, height=(cellwidth+1)*n, background="white") self.canvas.bind('', self.left) ## What should this do? self.canvas.bind('', self.edit_objects) self.canvas.bind('', self.add_object) if cellwidth: c = self.canvas for i in range(1, n+1): c.create_line(0, i*cellwidth, n*cellwidth, i*cellwidth) c.create_line(i*cellwidth, 0, i*cellwidth, n*cellwidth) c.pack(expand=1, fill='both') self.pack() def background_run(self): if self.running: self.env.step() ms = int(1000 * max(float(self.delay), 0.5)) self.after(ms, self.background_run) def run(self): print 'run' self.running = 1 self.background_run() def stop(self): print 'stop' self.running = 0 def left(self, event): print 'left at ', event.x/50, event.y/50 def edit_objects(self, event): """Choose an object within radius and edit its fields.""" pass def add_object(self, event): ## This is supposed to pop up a menu of Object classes; you choose the one ## You want to put in this square. Not working yet. tx, ty = event.x + self.winfo_rootx(), event.y + self.winfo_rooty() px, py = event.x/50, event.y/50 x, y = px * 50, py * 50 menu = tk.Menu(self, title='Edit (%d, %d)' % (px, py)) items = ['Wumpus', 'Pit', 'Agent', 'Gold', None, 'Monkey'] for (txt, cmd) in [(item, lambda item=item: self.makeObject(item, px, py)) for item in items]: if txt: menu.add_command(label=txt, command=cmd) else: menu.add_separator() menu.tk_popup(tx, ty) def makeObject(self, item, px, py): x, y = px * 50, py * 50 im = Image.open("../images/%s.gif" % item.lower()) im = im.resize( (48, 48), Image.BILINEAR ) image=PhotoImage(im) self.canvas.create_image(x+2,y+2,anchor=tk.NW,image=image) for obj in self.env.object_classes: if obj.__name__ == item: self.env.add_object( obj(image), (px, py)) return #v = VacuumEnvironment(); w1 = EnvFrame(v); e = WumpusEnvironment(); w2 = EnvFrame(e); pyrobot/aima/boggle.py0100644000076400003100000001310710144027257014760 0ustar dblankfaculty"""Generate high-scoring boards in the game of Boggle. A good domain for iterative-repair and related search tehniques, as suggested by Justin Boyan.""" import random, time, bisect, math, string ##_____________________________________________________________________________ cubes16 = ['FORIXB', 'MOQABJ', 'GURILW', 'SETUPL', 'CMPDAE', 'ACITAO', 'SLCRAE', 'ROMASH', 'NODESW', 'HEFIYE', 'ONUDTK', 'TEVIGN', 'ANEDVZ', 'PINESH', 'ABILYT', 'GKYLEU'] def random_board(n=4): "Return a random board of size n x n." cubes = [cubes16[i % 16] for i in range(n*n)] random.shuffle(cubes) return map(random.choice, cubes) def board(str): "Return a board made from the letters in str." return [c.upper() for c in str if c in string.letters] ## The best 5x5 board found by Boyan, with our word list we get ## 2274 words, for a score of 9837 boyan_best = board('RSTCS DEIAE GNLRP EATES MSSID') def print_board(board): n2 = len(board); n = exact_sqrt(n2) for i in range(n2): if i % n == 0: print if board[i] == 'Q': print 'Qu', else: print str(board[i]) + ' ', print def compute_neighbors(n2, cache={}): if cache.get(n2): return cache.get(n2) n = exact_sqrt(n2) neighbors = [None] * n2 for i in range(n2): neighbors[i] = [] on_top = i < n on_bottom = i >= n2 - n on_left = i % n == 0 on_right = (i+1) % n == 0 if not on_top: neighbors[i].append(i - n) if not on_left: neighbors[i].append(i - n - 1) if not on_right: neighbors[i].append(i - n + 1) if not on_bottom: neighbors[i].append(i + n) if not on_left: neighbors[i].append(i + n - 1) if not on_right: neighbors[i].append(i + n + 1) if not on_left: neighbors[i].append(i - 1) if not on_right: neighbors[i].append(i + 1) cache[n2] = neighbors return neighbors def exact_sqrt(n2): "If n2 is a perfect square, return its square root, else raise error." n = int(math.sqrt(n2)) assert n * n == n2 return n ##_____________________________________________________________________________ ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' class Wordlist: """This class holds a list of words. You can use (word in wordlist) to check if a word is in the list, or wordlist.lookup(prefix) to see if prefix starts any of the words in the list.""" def __init__(self, filename, min_len=3): lines = open(filename).read().upper().split() self.words = [word for word in lines if len(word) >= min_len] self.words.sort() self.bounds = {} for c in ALPHABET: c2 = chr(ord(c) + 1) self.bounds[c] = (bisect.bisect(self.words, c), bisect.bisect(self.words, c2)) def lookup(self, prefix, lo=0, hi=None): """See if prefix is in dictionary, as a full word or as a prefix. Return two values: the first is the lowest i such that words[i].startswith(prefix), or is None; the second is True iff prefix itslef is in the Wordlist.""" words = self.words i = bisect.bisect_left(words, prefix, lo, hi) if i < len(words) and words[i].startswith(prefix): return i, (words[i] == prefix) else: return None, False def __contains__(self, word): return self.words[bisect.bisect_left(self.words, word)] == word def __len__(self): return len(self.words) wordlist = Wordlist("../data/wordlist") ##_____________________________________________________________________________ class BoggleFinder: def __init__(self, wordlist=wordlist): self.wordlist = wordlist self.found = {} def set_board(self, board=None): if board is None: board = random_board() self.board = board self.neighbors = compute_neighbors(len(board)) self.found = {} for i in range(len(board)): lo, hi = self.wordlist.bounds[board[i]] self.find(lo, hi, i, [], '') return self def find(self, lo, hi, i, visited, prefix): if i in visited: return wordpos, is_word = self.wordlist.lookup(prefix, lo, hi) if wordpos is not None: if is_word: self.found[prefix] = True visited.append(i) c = self.board[i] if c == 'Q': c = 'QU' prefix += c for j in self.neighbors[i]: self.find(wordpos, hi, j, visited, prefix) visited.pop() def count(self): return len(self.found) def words(self): return self.found.keys() scores = [0, 0, 0, 0, 1, 2, 3, 5] + [11] * 100 def score(self): return sum([self.scores[len(w)] for w in self.words()]) def __len__(self): return len(self.found) ##_____________________________________________________________________________ def boggle_hill_climbing(n=5, ntimes=1000, print_it=True): finder = BoggleFinder() board, best = random_board(n), 0 for _ in range(ntimes): i, c = mutate(board) new = len(finder.set_board(board)) if new > best: print best, new best = new else: board[i] = c ## Change back if print_it: print_board(board) return board, best def mutate(board): i = random.randrange(len(board)) #c = random.choice(random.choice(cubes16)) c = random.choice(boyan_best) board[i] = c return i, c pyrobot/aima/csp.py0100644000076400003100000004657110144027257014321 0ustar dblankfaculty"""CSP (Constraint Satisfaction Problems) problems and solvers. (Chapter 5).""" from __future__ import generators from utils import * import search import types class CSP(search.Problem): """This class describes finite-domain Constraint Satisfaction Problems. A CSP is specified by the following three inputs: vars A list of variables; each is atomic (e.g. int or string). domains A dict of {var:[possible_value, ...]} entries. neighbors A dict of {var:[var,...]} that for each variable lists the other variables that participate in constraints. constraints A function f(A, a, B, b) that returns true if neighbors A, B satisfy the constraint when they have values A=a, B=b In the textbook and in most mathematical definitions, the constraints are specified as explicit pairs of allowable values, but the formulation here is easier to express and more compact for most cases. (For example, the n-Queens problem can be represented in O(n) space using this notation, instead of O(N^4) for the explicit representation.) In terms of describing the CSP as a problem, that's all there is. However, the class also supports data structures and methods that help you solve CSPs by calling a search function on the CSP. Methods and slots are as follows, where the argument 'a' represents an assignment, which is a dict of {var:val} entries: assign(var, val, a) Assign a[var] = val; do other bookkeeping unassign(var, a) Do del a[var], plus other bookkeeping nconflicts(var, val, a) Return the number of other variables that conflict with var=val curr_domains[var] Slot: remaining consistent values for var Used by constraint propagation routines. The following methods are used only by graph_search and tree_search: succ() Return a list of (action, state) pairs goal_test(a) Return true if all constraints satisfied The following are just for debugging purposes: nassigns Slot: tracks the number of assignments made display(a) Print a human-readable representation """ def __init__(self, vars, domains, neighbors, constraints): "Construct a CSP problem. If vars is empty, it becomes domains.keys()." vars = vars or domains.keys() update(self, vars=vars, domains=domains, neighbors=neighbors, constraints=constraints, initial={}, curr_domains=None, pruned=None, nassigns=0) def assign(self, var, val, assignment): """Add {var: val} to assignment; Discard the old value if any. Do bookkeeping for curr_domains and nassigns.""" self.nassigns += 1 assignment[var] = val if self.curr_domains: if self.fc: self.forward_check(var, val, assignment) if self.mac: AC3(self, [(Xk, var) for Xk in self.neighbors[var]]) def unassign(self, var, assignment): """Remove {var: val} from assignment; that is backtrack. DO NOT call this if you are changing a variable to a new value; just call assign for that.""" if var in assignment: # Reset the curr_domain to be the full original domain if self.curr_domains: self.curr_domains[var] = self.domains[var][:] del assignment[var] def nconflicts(self, var, val, assignment): "Return the number of conflicts var=val has with other variables." # Subclasses may implement this more efficiently def conflict(var2): val2 = assignment.get(var2, None) return val2 != None and not self.constraints(var, val, var2, val2) return count_if(conflict, self.neighbors[var]) def forward_check(self, var, val, assignment): "Do forward checking (current domain reduction) for this assignment." if self.curr_domains: # Restore prunings from previous value of var for (B, b) in self.pruned[var]: self.curr_domains[B].append(b) self.pruned[var] = [] # Prune any other B=b assignement that conflict with var=val for B in self.neighbors[var]: if B not in assignment: for b in self.curr_domains[B][:]: if not self.constraints(var, val, B, b): self.curr_domains[B].remove(b) self.pruned[var].append((B, b)) def display(self, assignment): "Show a human-readable representation of the CSP." # Subclasses can print in a prettier way, or display with a GUI print 'CSP:', self, 'with assignment:', assignment ## These methods are for the tree and graph search interface: def succ(self, assignment): "Return a list of (action, state) pairs." if len(assignment) == len(self.vars): return [] else: var = find_if(lambda v: v not in assignment, self.vars) result = [] for val in self.domains[var]: if self.nconflicts(self, var, val, assignment) == 0: a = assignment.copy; a[var] = val result.append(((var, val), a)) return result def goal_test(self, assignment): "The goal is to assign all vars, with all constraints satisfied." return (len(assignment) == len(self.vars) and every(lambda var: self.nconflicts(var, assignment[var], assignment) == 0, self.vars)) ## This is for min_conflicts search def conflicted_vars(self, current): "Return a list of variables in current assignment that are in conflict" return [var for var in self.vars if self.nconflicts(var, current[var], current) > 0] #______________________________________________________________________________ # CSP Backtracking Search def backtracking_search(csp, mcv=False, lcv=False, fc=False, mac=False): """Set up to do recursive backtracking search. Allow the following options: mcv - If true, use Most Constrained Variable Heuristic lcv - If true, use Least Constraining Value Heuristic fc - If true, use Forward Checking mac - If true, use Maintaining Arc Consistency. [Fig. 5.3] Ex: backtracking_search(australia)""" if fc or mac: csp.curr_domains, csp.pruned = {}, {} for v in csp.vars: csp.curr_domains[v] = csp.domains[v][:] csp.pruned[v] = [] update(csp, mcv=mcv, lcv=lcv, fc=fc, mac=mac) return recursive_backtracking({}, csp) def recursive_backtracking(assignment, csp): """Search for a consistent assignment for the csp. Each recursive call chooses a variable, and considers values for it.""" if len(assignment) == len(csp.vars): return assignment var = select_unassigned_variable(assignment, csp) for val in order_domain_values(var, assignment, csp): if csp.fc or csp.nconflicts(var, val, assignment) == 0: csp.assign(var, val, assignment) result = recursive_backtracking(assignment, csp) if result is not None: return result csp.unassign(var, assignment) return None def select_unassigned_variable(assignment, csp): "Select the variable to work on next. Find" if csp.mcv: # Most Constrained Variable unassigned = [v for v in csp.vars if v not in assignment] return argmin_random_tie(unassigned, lambda var: -num_legal_values(csp, var, assignment)) else: # First unassigned variable for v in csp.vars: if v not in assignment: return v def order_domain_values(var, assignment, csp): "Decide what order to consider the domain variables." if csp.curr_domains: domain = csp.curr_domains[var] else: domain = csp.domains[var][:] if csp.lcv: # If LCV is specified, consider values with fewer conflicts first domain.sort(comparer(lambda val: csp.nconflicts(var, val, assignment))) while domain: yield domain.pop() def num_legal_values(csp, var, assignment): if csp.curr_domains: return len(csp.curr_domains[var]) else: return count_if(lambda val: csp.nconflicts(var, val, assignment) == 0, csp.domains[var]) #______________________________________________________________________________ # Constraint Propagation with AC-3 def AC3(csp, queue=None): """[Fig. 5.7]""" if queue == None: queue = [(Xi, Xk) for Xi in csp.vars for Xk in csp.neighbors[Xi]] while queue: (Xi, Xj) = queue.pop() if remove_inconsistent_values(csp, Xi, Xj): for Xk in csp.neighbors[Xi]: queue.append((Xk, Xi)) def remove_inconsistent_values(csp, Xi, Xj): "Return true if we remove a value." removed = False for x in csp.curr_domains[Xi][:]: # If Xi=x conflicts with Xj=y for every possible y, eliminate Xi=x if every(lambda y: not csp.constraints(Xi, x, Xj, y), csp.curr_domains[Xj]): csp.curr_domains[Xi].remove(x) removed = True return removed #______________________________________________________________________________ # Min-conflicts hillclimbing search for CSPs def min_conflicts(csp, max_steps=1000000): """Solve a CSP by stochastic hillclimbing on the number of conflicts. Ex: min_conflicts(australia); min_conflicts(usa)""" # Generate a complete assignement for all vars (probably with conflicts) current = {}; csp.current = current for var in csp.vars: val = min_conflicts_value(csp, var, current) csp.assign(var, val, current) # Now repeapedly choose a random conflicted variable and change it for i in range(max_steps): conflicted = csp.conflicted_vars(current) if not conflicted: return current var = random.choice(conflicted) val = min_conflicts_value(csp, var, current) csp.assign(var, val, current) return None def min_conflicts_value(csp, var, current): """Return the value that will give var the least number of conflicts. If there is a tie, choose at random.""" return argmin_random_tie(csp.domains[var], lambda val: csp.nconflicts(var, val, current)) #______________________________________________________________________________ # Map-Coloring Problems class UniversalDict: """A universal dict maps any key to the same value. We use it here as the domains dict for CSPs in which all vars have the same domain. Ex: d = UniversalDict(42); d['life'] ==> 42""" def __init__(self, value): self.value = value def __getitem__(self, key): return self.value def __repr__(self): return '{Any: %r}' % self.value def different_values_constraint(A, a, B, b): "A constraint saying two neighboring variables must differ in value." return a != b def MapColoringCSP(colors, neighbors): """Make a CSP for the problem of coloring a map with different colors for any two adjacent regions. Arguments are a list of colors, and a dict of {region: [neighbor,...]} entries. This dict may also be specified as a string of the form defined by parse_neighbors""" if isinstance(neighbors, str): neighbors = parse_neighbors(neighbors) return CSP(neighbors.keys(), UniversalDict(colors), neighbors, different_values_constraint) def parse_neighbors(neighbors, vars=[]): """Convert a string of the form 'X: Y Z; Y: Z' into a dict mapping regions to neighbors. The syntax is a region name followed by a ':' followed by zero or more region names, followed by ';', repeated for each region name. If you say 'X: Y' you don't need 'Y: X'. parse_neighbors('X: Y Z; Y: Z') ==> {'Y': ['X', 'Z'], 'X': ['Y', 'Z'], 'Z': ['X', 'Y']}""" dict = DefaultDict([]) for var in vars: dict[var] = [] specs = [spec.split(':') for spec in neighbors.split(';')] for (A, Aneighbors) in specs: A = A.strip(); dict.setdefault(A, []) for B in Aneighbors.split(): dict[A].append(B) dict[B].append(A) return dict australia = MapColoringCSP(list('RGB'), 'SA: WA NT Q NSW V; NT: WA Q; NSW: Q V; T: ') usa = MapColoringCSP(list('RGBY'), """WA: OR ID; OR: ID NV CA; CA: NV AZ; NV: ID UT AZ; ID: MT WY UT; UT: WY CO AZ; MT: ND SD WY; WY: SD NE CO; CO: NE KA OK NM; NM: OK TX; ND: MN SD; SD: MN IA NE; NE: IA MO KA; KA: MO OK; OK: MO AR TX; TX: AR LA; MN: WI IA; IA: WI IL MO; MO: IL KY TN AR; AR: MS TN LA; LA: MS; WI: MI IL; IL: IN; IN: KY; MS: TN AL; AL: TN GA FL; MI: OH; OH: PA WV KY; KY: WV VA TN; TN: VA NC GA; GA: NC SC FL; PA: NY NJ DE MD WV; WV: MD VA; VA: MD DC NC; NC: SC; NY: VT MA CA NJ; NJ: DE; DE: MD; MD: DC; VT: NH MA; MA: NH RI CT; CT: RI; ME: NH; HI: ; AK: """) #______________________________________________________________________________ # n-Queens Problem def queen_constraint(A, a, B, b): """Constraint is satisfied (true) if A, B are really the same variable, or if they are not in the same row, down diagonal, or up diagonal.""" return A == B or (a != b and A + a != B + b and A - a != B - b) class NQueensCSP(CSP): """Make a CSP for the nQueens problem for search with min_conflicts. Suitable for large n, it uses only data structures of size O(n). Think of placing queens one per column, from left to right. That means position (x, y) represents (var, val) in the CSP. The main structures are three arrays to count queens that could conflict: rows[i] Number of queens in the ith row (i.e val == i) downs[i] Number of queens in the \ diagonal such that their (x, y) coordinates sum to i ups[i] Number of queens in the / diagonal such that their (x, y) coordinates have x-y+n-1 = i We increment/decrement these counts each time a queen is placed/moved from a row/diagonal. So moving is O(1), as is nconflicts. But choosing a variable, and a best value for the variable, are each O(n). If you want, you can keep track of conflicted vars, then variable selection will also be O(1). Ex: backtracking_search(NQueensCSP(8)) min_conflicts(NQueensCSP(8))""" def __init__(self, n): """Initialize data structures for n Queens.""" CSP.__init__(self, range(n), UniversalDict(range(n)), UniversalDict(range(n)), queen_constraint) update(self, rows=[0]*n, ups=[0]*(2*n - 1), downs=[0]*(2*n - 1)) def nconflicts(self, var, val, assignment): """The number of conflicts, as recorded with each assignment. Count conflicts in row and in up, down diagonals. If there is a queen there, it can't conflict with itself, so subtract 3.""" n = len(self.vars) c = self.rows[val] + self.downs[var+val] + self.ups[var-val+n-1] if assignment.get(var, None) == val: c -= 3 return c def assign(self, var, val, assignment): "Assign var, and keep track of conflicts." oldval = assignment.get(var, None) if val != oldval: if oldval is not None: # Remove old val if there was one self.record_conflict(assignment, var, oldval, -1) self.record_conflict(assignment, var, val, +1) CSP.assign(self, var, val, assignment) def unassign(self, var, assignment): "Remove var from assignment (if it is there) and track conflicts." if var in assignment: self.record_conflict(assignment, var, assignment[var], -1) CSP.unassign(self, var, assignment) def record_conflict(self, assignment, var, val, delta): "Record conflicts caused by addition or deletion of a Queen." n = len(self.vars) self.rows[val] += delta self.downs[var + val] += delta self.ups[var - val + n - 1] += delta def display(self, assignment): "Print the queens and the nconflicts values (for debugging)." n = len(self.vars) for val in range(n): for var in range(n): if assignment.get(var,'') == val: ch ='Q' elif (var+val) % 2 == 0: ch = '.' else: ch = '-' print ch, print ' ', for var in range(n): if assignment.get(var,'') == val: ch ='*' else: ch = ' ' print str(self.nconflicts(var, val, assignment))+ch, print #______________________________________________________________________________ # The Zebra Puzzle def Zebra(): "Return an instance of the Zebra Puzzle." Colors = 'Red Yellow Blue Green Ivory'.split() Pets = 'Dog Fox Snails Horse Zebra'.split() Drinks = 'OJ Tea Coffee Milk Water'.split() Countries = 'Englishman Spaniard Norwegian Ukranian Japanese'.split() Smokes = 'Kools Chesterfields Winston LuckyStrike Parliaments'.split() vars = Colors + Pets + Drinks + Countries + Smokes domains = {} for var in vars: domains[var] = range(1, 6) domains['Norwegian'] = [1] domains['Milk'] = [3] neighbors = parse_neighbors("""Englishman: Red; Spaniard: Dog; Kools: Yellow; Chesterfields: Fox; Norwegian: Blue; Winston: Snails; LuckyStrike: OJ; Ukranian: Tea; Japanese: Parliaments; Kools: Horse; Coffee: Green; Green: Ivory""", vars) for type in [Colors, Pets, Drinks, Countries, Smokes]: for A in type: for B in type: if A != B: if B not in neighbors[A]: neighbors[A].append(B) if A not in neighbors[B]: neighbors[B].append(A) def zebra_constraint(A, a, B, b, recurse=0): same = (a == b) next_to = abs(a - b) == 1 if A == 'Englishman' and B == 'Red': return same if A == 'Spaniard' and B == 'Dog': return same if A == 'Chesterfields' and B == 'Fox': return next_to if A == 'Norwegian' and B == 'Blue': return next_to if A == 'Kools' and B == 'Yellow': return same if A == 'Winston' and B == 'Snails': return same if A == 'LuckyStrike' and B == 'OJ': return same if A == 'Ukranian' and B == 'Tea': return same if A == 'Japanese' and B == 'Parliaments': return same if A == 'Kools' and B == 'Horse': return next_to if A == 'Coffee' and B == 'Green': return same if A == 'Green' and B == 'Ivory': return (a - 1) == b if recurse == 0: return zebra_constraint(B, b, A, a, 1) if ((A in Colors and B in Colors) or (A in Pets and B in Pets) or (A in Drinks and B in Drinks) or (A in Countries and B in Countries) or (A in Smokes and B in Smokes)): return not same raise 'error' return CSP(vars, domains, neighbors, zebra_constraint) def solve_zebra(algorithm=min_conflicts, **args): z = Zebra() ans = algorithm(z, **args) for h in range(1, 6): print 'House', h, for (var, val) in ans.items(): if val == h: print var, print return ans['Zebra'], ans['Water'], z.nassigns, ans, pyrobot/aima/docex.py0100644000076400003100000002010710144027257014621 0ustar dblankfaculty"""A framework for running unit test examples, written in docstrings. This lets you write 'Ex: sqrt(4) ==> 2; sqrt(-1) raises ValueError' in the docstring for sqrt, and then execute the examples as unit tests. This functionality is similar to Tim Peters' doctest module, but I started this before doctest became an official Python module. If you want more functionality and standardization, use doctest; if you want to make your docstrings shorter, you might want docex. (The name 'docex' connotes DOCstring EXamples, a similarity to doctest, the literal 'Ex:', and a certain package delivery service that also ends with 'ex', and offers fast reliable no-frills service.) From Python, when you want to test modules m1, m2, ... do: docex.Test([m1, m2, ...]) From the shell, when you want to test files *.py, do: python docex.py output-file *.py If output file ends in .htm or .html, it will be written in HTML. If output file is -, then standard output is used. For each module, Test looks at the __doc__ and _docex strings of the module itself, and of each member, and recursively for each member class. If a line in a docstring starts with r'^\s*Ex: ' (a line with blanks, then 'Ex: '), then the remainder of the string after the colon is treated as examples. Each line of the examples should conform to one of the following formats: (1) Blank line or a comment; these just get echoed verbatim to the log. (2) Of the form example1 ; example2 ; ... (3) Of the form 'x ==> y' for any expressions x and y. x is evaled and assigned to _, then y is evaled. If x != y, an error message is printed. (4) Of the form 'x raises y', for any statement x and expression y. First y is evaled to yield an exception type, then x is execed. If x doesn't raise the right exception, an error msg is printed. (5) Of the form 'statement'. Statement is execed for side effect. (6) Of the form 'expression'. Expression is evaled for side effect. My main reason for stubbornly sticking with my docex rather than converting to doctest is that I want docstrings to be brief. Compare doctest's 8-lines: >>> len('abc') 3 >>> len([]) 0 >>> len(5)) Traceback (most recent call last): ... TypeError: len() of unsized object with docex's 1-line: Ex: len('abc') ==> 3; len([]) ==> 0; len(5) raises TypeError """ import re, sys, types class Test: """A class to run test examples written in docstrings or in _docex.""" def __init__(self, modules=None, html=1, out=None, title='Docex Example Output'): if modules is None: modules = sys.modules.values() self.passed = self.failed = 0; self.dictionary = {} self.already_seen = {} self.html = html try: if out: sys.stdout = out self.writeln('', '<>\n
\n' % title)
            for module in modules:
                self.run_module(module)
            self.writeln(str(self), '
\n

', '

\n<